/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {

    // 一般的数值

    if ((nums.reduce((a, b) => a + b, 0)) % 2 > 0) {
        return false
    }

    nums.sort((a, b) => a - b)
    let halfSum = (nums.reduce((a, b) => a + b, 0)) / 2

    // 也就是这个时候j就是容量, 容量的循环就是0-j
    // nums中数字就是物品 就是物品0到物品len-1

    // 挡在dp[halfSum]这个份量的时候,价值正好也这么大, 说明就是有这样的数组
    const arr = new Array(halfSum).fill(0)
    const dp = Array.from({ length: nums.length }, () => [0, ...arr]);

    for (let j = 1; j < dp[0].length; j++) {
        if (nums[0] <= j) {
            dp[0][j] = nums[0]
        } else {
            dp[0][j] = 0
        }

    }

    for (let i = 1; i < dp.length; i++) {
        for (let j = 1; j < halfSum + 1; j++) {
            //  当前数值, dp[i][j]
            // 简单理解就是, 在重量为j时, 物品i,放和不放的最大价值
            // 先解释不放的最大价值
            // dp[i-1][j]

            // 放的最大价值
            // 就是上面 i-1 为上面一层, j-nums[i], 总重量-当前物品的重量
            // dp[i-1][j-nums[i]]+nums[i]
            // 这时候就一个需要考虑,就是j-nums[i]这个值一定要>=0,不然背包背不动

            if (j - nums[i] >= 0) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
            } else {
                dp[i][j] = dp[i - 1][j]
            }
        }

    }

    if (dp[nums.length - 1][halfSum] === halfSum) return true
    return false

};

let arr = [5, 1, 11, 5]
canPartition(arr)

